'''
Created on 11/12/2012

@author: greis
'''
from random import Random
"""
board = ["___","___","___"]

def countMovesLeft(board):
    count = 0
    for line in board:
        for column in line:
            if column == '_':
                count += 1
    return count

def isGoal(player,board):
    if (board[0][0] == player and board[0][1] == player and board[0][2] == player) or (board[1][0] == player and board[1][1] == player and board[1][2] == player) or (board[2][0] == player and board[2][1] == player and board[2][2] == player) or (board[0][0] == player and board[1][0] == player and board[2][0] == player) or (board[0][1] == player and board[1][1] == player and board[2][1] == player) or (board[0][2] == player and board[1][2] == player and board[2][2] == player) or (board[0][0] == player and board[1][1] == player and board[2][2] == player) or (board[0][2] == player and board[1][1] == player and board[2][0] == player):
        return True
    else:
        return False
    
def isLose(player,board):
    if player == 'X':
        player = 'O'
    else:
        player = 'X'
    return isGoal(player,board)
    
def isDraw(player,board):
    if countMovesLeft(board) == 0 and isGoal(player,board) == False and isLose(player,board) == False:
        return True
    else:
        return False
    
def getNextMove(player,board):
    count = 0
    newBoard = []
    moveLine = ''
    moveColumn = ''
    if player == 'X':
        for i in xrange(0, 3):
            line = board[i]
            newLine = ""
            for j in xrange(0, 3):
                column = line[j]
                if column == '_' and count == 0:
                    newLine += 'X' 
                    moveLine = i
                    moveColumn = j
                    count = 1 
                else:
                    newLine += column
            newBoard.append(newLine)
        #print str(moveLine)+" "+str(moveColumn)
    elif player == 'O':
        for i in xrange(0, 3):
            line = board[i]
            newLine = ""
            for j in xrange(0, 3):
                column = line[j]
                if column == '_' and count == 0:
                    newLine += 'O' 
                    moveLine = i
                    moveColumn = j
                    count = 1 
                else:
                    newLine += column
            newBoard.append(newLine)
        #print str(moveLine)+" "+str(moveColumn)
    action = (moveLine,moveColumn)
    return (newBoard,action,count)
"""     
##############################################################



###############################################################
import sys, inspect, heapq

def lookup(name, namespace):
    """
    Get a method or class from any imported module from its name.
    Usage: lookup(functionName, globals())
    """
    dots = name.count('.')
    if dots > 0:
        moduleName, objName = '.'.join(name.split('.')[:-1]), name.split('.')[-1]
        module = __import__(moduleName)
        return getattr(module, objName)
    else:
        modules = [obj for obj in namespace.values() if str(type(obj)) == "<type 'module'>"]
        options = [getattr(module, name) for module in modules if name in dir(module)]
        options += [obj[1] for obj in namespace.items() if obj[0] == name ]
        if len(options) == 1: return options[0]
        if len(options) > 1: raise Exception, 'Name conflict for %s'
        raise Exception, '%s not found as a method or class' % name

def raiseNotDefined():
    print "Method not implemented: %s" % inspect.stack()[1][3]
    sys.exit(1)
    
def nullHeuristic(self, state, problem=None):
    """
    A heuristic function estimates the cost from the current state to the nearest
    goal in the provided SearchProblem.  This heuristic is trivial.
    """
    return 0

class PriorityQueue:
    """
      Implements a priority queue data structure. Each inserted item
      has a priority associated with it and the client is usually interested
      in quick retrieval of the lowest-priority item in the queue. This
      data structure allows O(1) access to the lowest-priority item.

      Note that this PriorityQueue does not allow you to change the priority
      of an item.  However, you may insert the same item multiple times with
      different priorities.
    """
    def  __init__(self):
        self.heap = []

    def push(self, item, priority):
        pair = (priority,item)
        heapq.heappush(self.heap,pair)

    def pop(self):
        (priority,item) = heapq.heappop(self.heap)
        return item

    def isEmpty(self):
        return len(self.heap) == 0
    
class Agent:
    """
    An agent must define a getAction method, but may also define the
    following methods which will be called if they exist:

    def registerInitialState(self, state): # inspects the starting state
    """
    possibleAgentsIndex = ['X', 'O']
    
    def __init__(self, index=0):
        self.index = index
        
    def getAgentSymbol(self):
        return self.possibleAgentsIndex[self.index]
    
    def getOpponentIndex(self):
        if self.index == 0:
            return 1
        else:
            return 0
        
    def getOpponentSymbol(self):
        if self.index == 0:
            return self.possibleAgentsIndex[1]
        else:
            return self.possibleAgentsIndex[0]
        
    def getNumAgents(self):
        return len(self.possibleAgentsIndex)
        
    def countAgent(agentIndex, state):
        count = 0
        for line in state.board:
            count += line.count(agentIndex)
        return count
    countAgent = staticmethod( countAgent )
    
    def getAction(self, state):
        """
        The Agent will receive a GameState (from either {pacman, capture, sonar}.py) and
        must return an action from Directions.{North, South, East, West, Stop}
        """
        raiseNotDefined()
       
class Directions:
    NORTH = 'North'
    SOUTH = 'South'
    EAST = 'East'
    WEST = 'West'
    NORTHEAST = 'NorthEast'
    NORTHWEST = 'NorthWest'
    SOUTHEAST = 'SouthEast'
    SOUTHWEST = 'SouthWest'
    STOP = 'Stop'
    CENTER = 'Center'
    
class Actions:
    """
    Actions must define actions
    """
    ACTIONS = {Directions.NORTHWEST: (0,0),
               Directions.NORTH: (0,1),
               Directions.NORTHEAST: (0,2),
               Directions.WEST: (1,0),
               Directions.CENTER: (1,1),
               Directions.EAST: (1,2),
               Directions.SOUTHWEST: (2,0),
               Directions.SOUTH: (2,1),
               Directions.SOUTHEAST: (2,2)}
    TOLERANCE = .001
    possibleActions = [Directions.NORTHWEST, Directions.NORTH, Directions.NORTHEAST, Directions.WEST, Directions.CENTER, Directions.EAST, Directions.SOUTHWEST, Directions.SOUTH, Directions.SOUTHEAST]
    
    def findAction(line, column):
        action = [key for (key,value) in Actions.ACTIONS.items() if value == (line,column)]
        if len(action) > 0:
            action = action[0]
        return action
    findAction = staticmethod( findAction )
    
class State:
    """
    State must define a possible state
    """
    PROPERTIES = {}
    listWin = []
    listWin.append(["***","___","___"])
    listWin.append(["___","***","___"])
    listWin.append(["___","___","***"])
    listWin.append(["*__","*__","*__"])
    listWin.append(["_*_","_*_","_*_"])
    listWin.append(["__*","__*","__*"])
    listWin.append(["*__","_*_","__*"])
    listWin.append(["__*","_*_","__*"])
    def __init__(self, agentIndex, board=[]):
        self.board = board
        self.agent = Agent(agentIndex)
        self.numOfAgents = self.agent.getNumAgents()
    
    def compareState(self, otherState):
        """
        return 0 if this state is equal to otherState, -1 if its different
        """
        if self.board == otherState.board:
            return 0
        else:
            return -1
        
    def changeAgent(self):
        if self.agent.index == 0:
            self.agent.index = 1
        else:
            self.agent.index = 0
            
    def getLegalActions(self, agentIndex):
        """
        return a list of legal actions from the current state
        return [possibleAction]
        """
        """
        count = 0
        for line in self.board:
            for column in line:
                if column == '_':
                    count += 1
        """
        legalActions = []
        for i in xrange(0, 3):
            line = self.board[i]
            for j in xrange(0, 3):
                column = line[j]
                if column == '_':
                    #for action in Actions.ACTIONS.itervalues():
                    #    if action == (line,clumn):
                    #legalActions.append((line,column))
                    legalActions.append(Actions.findAction(i,j))
        return legalActions
        
    def basicHeuristicFunction(self, state):
        """
          This default Heuristic function just returns the score of the state.
          This Heuristic function is meant to be very basic.
        """
        return 0
    
    def generateSuccessor(self, agentIndex, action):
        #return self.getSuccState(None, None, Actions.ACTIONS[action])[0][0]
        count = 0
        move = Actions.ACTIONS[action]
        state = State(agentIndex, self.board)
        newState = State(agentIndex, [])
        for i in xrange(0, 3):
            line = state.board[i]
            newLine = ""
            for j in xrange(0, 3):
                column = line[j]
                if column == '_' and count == 0 and move[0] == i and move[1] == j:
                    newLine += newState.agent.getAgentSymbol()
                    count = 1
                else:
                    newLine += column
            newState.board.append(newLine)
        return newState
    
    def getSuccessors(self):
        """
        Returns successor states, the actions they require, and a cost of for taking this action.
             For a given state, this should return a list of triples,
         (successor, action, stepCost), where 'successor' is a
         successor to the current state, 'action' is the action
         required to get there, and 'stepCost' is the incremental
         cost of expanding to that successor
        """
        successors = []
        hasMove = True
        currentState = None
        fullState = None
        while hasMove:
            move = self.getSuccState(currentState, fullState)
            if move[0][2] > 0:
                successors.append(move[0])
                currentState = move[0][0]
                fullState = move[1]
                #currentState.changeAgent()
            else:
                hasMove = False
        #print "Move: ", move, "full: ", move[1].board
        return successors
                
    def getSuccState(self, currState=None, fullState=None, cell=('','')):
        count = 0
        state = State(self.agent.index, self.board)
        if currState == None:
            currState = state
        if fullState == None:
            fullState = state
        newFullState = State(currState.agent.index,[])
        newState = State(currState.agent.index,[])
        moveLine = ''
        moveColumn = ''
        for i in xrange(0, 3):
            line = state.board[i]
            #currLine = currState.board[i]
            fullLine = fullState.board[i]
            newFullLine = ""
            newLine = ""
            for j in xrange(0, 3):
                column = line[j]
                #currColumn = currLine[j]
                fullColumn = fullLine[j]
                if fullColumn == '_' and count == 0:# and ((cell[0] <> '' and cell[1] <> '') or (cell[0] == i and cell[1] == j)):
                    newLine += currState.agent.getAgentSymbol()
                    newFullLine += currState.agent.getAgentSymbol()
                    moveLine = i
                    moveColumn = j
                    count = 1 
                else:
                    newLine += column
                    newFullLine += fullColumn
            newState.board.append(newLine)
            newFullState.board.append(newFullLine)
        #numXO = (newFullState.board[0].count('X')+newFullState.board[1].count('X')+newFullState.board[2].count('X'), newFullState.board[0].count('O')+newFullState.board[1].count('O')+newFullState.board[2].count('O'))
        #print "numXO: ", numXO
        newState.changeAgent()
        #print "Action: ", moveLine,moveColumn
        #action = (moveLine,moveColumn)
        action = Actions.findAction(moveLine,moveColumn)
        #return ((newState,action,count,newState.agent.index,(moveLine,moveColumn),newState.board),newFullState)
        return ((newState,action,count),newFullState)
    
    def getNextMove(self):
        count = 0
        newState = State(self.agent.index,[])
        moveLine = ''
        moveColumn = ''
        for i in xrange(0, 3):
            line = self.board[i]
            newLine = ""
            for j in xrange(0, 3):
                column = line[j]
                if column == '_' and count == 0:
                    newLine += self.agent.getAgentSymbol()
                    moveLine = i
                    moveColumn = j
                    count = 1 
                else:
                    newLine += column
            newState.board.append(newLine)
        action = (moveLine,moveColumn)
        return (newState,action,count)
        
    def countMovesLeft(self):
        count = 0
        for line in self.board:
            for column in line:
                if column == '_':
                    count += 1
        return count

    def isGoalState(self):
        return self.isGoal()
    
    def isWin(self):
        return self.isGoal()

    def isGoal(self):
        if (self.board[0][0] == self.agent.getAgentSymbol() and self.board[0][1] == self.agent.getAgentSymbol() and self.board[0][2] == self.agent.getAgentSymbol()) or (self.board[1][0] == self.agent.getAgentSymbol() and self.board[1][1] == self.agent.getAgentSymbol() and self.board[1][2] == self.agent.getAgentSymbol()) or (self.board[2][0] == self.agent.getAgentSymbol() and self.board[2][1] == self.agent.getAgentSymbol() and self.board[2][2] == self.agent.getAgentSymbol()) or (self.board[0][0] == self.agent.getAgentSymbol() and self.board[1][0] == self.agent.getAgentSymbol() and self.board[2][0] == self.agent.getAgentSymbol()) or (self.board[0][1] == self.agent.getAgentSymbol() and self.board[1][1] == self.agent.getAgentSymbol() and self.board[2][1] == self.agent.getAgentSymbol()) or (self.board[0][2] == self.agent.getAgentSymbol() and self.board[1][2] == self.agent.getAgentSymbol() and self.board[2][2] == self.agent.getAgentSymbol()) or (self.board[0][0] == self.agent.getAgentSymbol() and self.board[1][1] == self.agent.getAgentSymbol() and self.board[2][2] == self.agent.getAgentSymbol()) or (self.board[0][2] == self.agent.getAgentSymbol() and self.board[1][1] == self.agent.getAgentSymbol() and self.board[2][0] == self.agent.getAgentSymbol()):
            return True
        else:
            return False
    
    def isLose(self):
        if self.agent.index == 0:
            newState = State(1, self.board)
        else:
            newState = State(0, self.board)
        return newState.isGoal()
    
    def isDraw(self):
        if self.countMovesLeft() == 0 and self.isGoal() == False and self.isLose() == False:
            return True
        else:
            return False
    
    def getCostOfActions(self, actions):
        """
        Returns the cost of a particular sequence of actions.  If those actions
        include an illegal move, return 999999
        """
        return len(actions)
    
    def getScore(self):
        score = 1
        points = 1

        
        for win in self.listWin:
            point = 1
            for i in xrange(0, 3):
                line = self.board[i]
                for j in xrange(0, 3):
                    column = line[j]
                    #print (i,j),"Win: ", win[i][j], "Board: ", self.board[i][j], "Agent: ", self.agent.getAgentSymbol()
                    if win[i][j] == '*' and self.board[i][j] == self.agent.getAgentSymbol():
                        point += 1
                        #score += 1
                    if win[i][j] == '*' and self.board[i][j] == self.agent.getOpponentSymbol():
                        point -= 1
                        #score -= 1
                        #print (i,j),"Win: ", win[i][j], "Board: ", self.board[i][j], "Agent: ", self.agent.getAgentSymbol(), "Point: ", point
            if point > points:
                points = point
            #if point == 3:
                #continue
        score = (score) * points
        
        #print "Score: ", score
        return score
    
class Problem_OLD:
    """
    A search problem defines the state space, start state, goal test,
    successor function and cost function.
    """
    def __init__(self, state):
        self.startState = state
    
    def getSuccessors(self, state):
        """
        Returns successor states, the actions they require, and a cost of for taking this action.
             For a given state, this should return a list of triples,
         (successor, action, stepCost), where 'successor' is a
         successor to the current state, 'action' is the action
         required to get there, and 'stepCost' is the incremental
         cost of expanding to that successor
        """
        successors = []
        hasMove = True
        currentState = None
        fullState = None
        while hasMove:
            move = self.getSuccState(state, currentState, fullState)
            if move[0][2] > 0:
                successors.append(move[0])
                currentState = move[0][0]
                fullState = move[1]
                #currentState.changeAgent()
            else:
                hasMove = False
        #print "Move: ", move, "full: ", move[1].board
        return successors
                
    def getSuccState(self, state, currState=None, fullState=None, cell=('','')):
        count = 0
        if currState == None:
            currState = state
        if fullState == None:
            fullState = state
        newFullState = State(currState.agent.index,[])
        newState = State(currState.agent.index,[])
        moveLine = ''
        moveColumn = ''
        for i in xrange(0, 3):
            line = state.board[i]
            #currLine = currState.board[i]
            fullLine = fullState.board[i]
            newFullLine = ""
            newLine = ""
            for j in xrange(0, 3):
                column = line[j]
                #currColumn = currLine[j]
                fullColumn = fullLine[j]
                if fullColumn == '_' and count == 0 and ((cell[0] <> '' and cell[1] <> '') or (cell[0] == i and cell[1] == j)):
                    newLine += currState.agent.index
                    newFullLine += currState.agent.index
                    moveLine = i
                    moveColumn = j
                    count = 1 
                else:
                    newLine += column
                    newFullLine += fullColumn
            newState.board.append(newLine)
            newFullState.board.append(newFullLine)
        #numXO = (newFullState.board[0].count('X')+newFullState.board[1].count('X')+newFullState.board[2].count('X'), newFullState.board[0].count('O')+newFullState.board[1].count('O')+newFullState.board[2].count('O'))
        #print "numXO: ", numXO
        newState.changeAgent()
        #action = (moveLine,moveColumn)
        action = Actions.findAction(moveLine,moveColumn)
        #return ((newState,action,count,newState.agent.index,(moveLine,moveColumn),newState.board),newFullState)
        return ((newState,action,count),newFullState)
    
    def getNextMove(self, state):
        count = 0
        newState = State(state.agent.index,[])
        moveLine = ''
        moveColumn = ''
        for i in xrange(0, 3):
            line = state.board[i]
            newLine = ""
            for j in xrange(0, 3):
                column = line[j]
                if column == '_' and count == 0:
                    newLine += state.agent.index 
                    moveLine = i
                    moveColumn = j
                    count = 1 
                else:
                    newLine += column
            newState.board.append(newLine)
        action = (moveLine,moveColumn)
        return (newState,action,count)
    
    def getStartState(self):
        """
        retorna o State inicial
        """
        return self.startState
        
    def countMovesLeft(self, state):
        count = 0
        for line in state.board:
            for column in line:
                if column == '_':
                    count += 1
        return count

    def isGoalState(self, state):
        return self.isGoal(state)

    def isGoal(self, state):
        if (state.board[0][0] == state.agent.index and state.board[0][1] == state.agent.index and state.board[0][2] == state.agent.index) or (state.board[1][0] == state.agent.index and state.board[1][1] == state.agent.index and state.board[1][2] == state.agent.index) or (state.board[2][0] == state.agent.index and state.board[2][1] == state.agent.index and state.board[2][2] == state.agent.index) or (state.board[0][0] == state.agent.index and state.board[1][0] == state.agent.index and state.board[2][0] == state.agent.index) or (state.board[0][1] == state.agent.index and state.board[1][1] == state.agent.index and state.board[2][1] == state.agent.index) or (state.board[0][2] == state.agent.index and state.board[1][2] == state.agent.index and state.board[2][2] == state.agent.index) or (state.board[0][0] == state.agent.index and state.board[1][1] == state.agent.index and state.board[2][2] == state.agent.index) or (state.board[0][2] == state.agent.index and state.board[1][1] == state.agent.index and state.board[2][0] == state.agent.index):
            return True
        else:
            return False
    
    def isLose(self, state):
        if state.agent.index == 'X':
            newState = State('O', state.board)
        else:
            newState = State('X', state.board)
        return self.isGoal(newState)
    
    def isDraw(self, state):
        if self.countMovesLeft(state) == 0 and self.isGoal(state) == False and self.isLose(state) == False:
            return True
        else:
            return False
    
    def getCostOfActions(self, actions):
        """
        Returns the cost of a particular sequence of actions.  If those actions
        include an illegal move, return 999999
        """
        return len(actions)
        
    
def scoreEvaluationFunction(currentGameState):
    """
      This default evaluation function just returns the score of the state.
      The score is the same one displayed in the Pacman GUI.
    
      This evaluation function is meant for use with adversarial search agents
      (not reflex agents).
    """
    return currentGameState.getScore()

class MultiAgentSearchAgent(Agent):
    """
      This class provides some common elements to all of your
      multi-agent searchers.  Any methods defined here will be available
      to the MinimaxPacmanAgent, AlphaBetaPacmanAgent & ExpectimaxPacmanAgent.
    
      You *do not* need to make any changes here, but you can if you want to
      add functionality to all your adversarial search agents.  Please do not
      remove anything, however.
    
      Note: this is an abstract class: one that should not be instantiated.  It's
      only partially specified, and designed to be extended.  Agent (game.py)
      is another abstract class.
    """
    
    def __init__(self, index=0, evalFn = 'scoreEvaluationFunction', depth = '3'):
        self.index = index
        self.evaluationFunction = lookup(evalFn, globals())
        self.depth = int(depth)

class ExpectimaxAgent(MultiAgentSearchAgent):
    """
      Your expectimax agent (question 4)
    """
    
    def getAction(self, gameState):
        """
          Returns the expectimax action using self.depth and self.evaluationFunction
        
          All ghosts should be modeled as choosing uniformly at random from their
          legal moves.
        """
        "*** YOUR CODE HERE ***"
        gameAgent = gameState.agent
        numAgents = gameAgent.getNumAgents() # get the number of agents in the game
        legalMoves = gameState.getLegalActions(self.index) #get the legal actions available fot the current agent
        #if Directions.STOP in legalMoves: legalMoves.remove(Directions.STOP)
        successorGameStatesAction = [(gameState.generateSuccessor(self.index, nextMove),nextMove) for nextMove in legalMoves] #get the firts nodes for the root
        valueAction = [self.expectimaxActionsValue(successorGameState, succMove, self.index, ((self.depth*numAgents)-1), numAgents) for successorGameState,succMove in successorGameStatesAction] #call expctimax for each one of the firsts nodes of the root
        bestAction = legalMoves[valueAction.index(max(valueAction))] #get the best move for the expctimax function
        return bestAction #return the best move based on the expectimax value
      
    def expectimaxActionsValue(self, currentGameState, nextMove, index, depth, numAgents):
        index += 1 
        if index >= numAgents: index = 0 #reset the index every time it reach the last agent
        legalMoves = currentGameState.getLegalActions(index) #get the legal actions available fot the current agent
        #if Directions.STOP in legalMoves: legalMoves.remove(Directions.STOP)
        successorGameStatesAction = [(currentGameState.generateSuccessor(index, nextMove),nextMove) for nextMove in legalMoves] #get the nexts gamestates based on the possible moves for the current gamestate
        if depth < 1 or currentGameState.isWin() or currentGameState.isLose(): #if it's the end of the game, or if reach the end of the limit depth (it's the terminal node), get the evaluationFunction and the action
            valueAction = self.evaluationFunction(currentGameState)
        elif index == 0: #else, get the max value for pacman, or the expectation value for the ghosts
            valueAction = max([self.expectimaxActionsValue(successorGameState, succMove, index, depth-1, numAgents) for successorGameState,succMove in successorGameStatesAction])
        else:
            valueActions = [self.expectimaxActionsValue(successorGameState, succMove, index, depth-1, numAgents) for successorGameState,succMove in successorGameStatesAction]
            if len(valueActions) > 0:
                valueAction = sum(valueActions)/len(valueActions)
            else:
                valueAction = 0
        return valueAction  #and return the value with its move

class Search:
    
    def aStarGenericSearch(self, state, heuristic=nullHeuristic):
        return self.genericSearch(state, PriorityQueue(), 2, (lambda x: heuristic(x,state))); 
    
    def genericSearch(self, state, fringe, searchtype, heuristicValue=(lambda x:0)):
        """
        Generic search method
        """
        #gameState = state.getStartState()
        currentState=state
        linkedList = {(currentState):({},None,currentState,None,0,0)}
        if currentState.isGoalState():
            return []
        else:
            closedSet=set()
            node = currentState
            if searchtype == 2:
                fringe.push(node,0+heuristicValue(currentState))
            else:
                fringe.push(node)
            while not fringe.isEmpty():
                currentState=fringe.pop()
                #if problem.isGoalState(currentState):
                if currentState.isGoalState():
                    path = self.pathBuilder(linkedList,currentState,[])
                    path.reverse()
                    #print "Win: ", currentState.board
                    numXO = (currentState.board[0].count('X')+currentState.board[1].count('X')+currentState.board[2].count('X'), currentState.board[0].count('O')+currentState.board[1].count('O')+currentState.board[2].count('O'))
                    #print "numXO: ", numXO
                    return path
                elif currentState in closedSet:# or problem.isLose(currentState) or problem.isDraw(currentState):
                    continue       
                else:
                    closedSet.add(currentState)
                    succs = currentState.getSuccessors()
                    for nextState,nextMove,nextCost in succs:
                        #print "Board: ", nextState.board, nextState.agent.index
                        numXO = (nextState.board[0].count('X')+nextState.board[1].count('X')+nextState.board[2].count('X'), nextState.board[0].count('O')+nextState.board[1].count('O')+nextState.board[2].count('O'))
                        #print "numXO: ", numXO
                        cumulativeCost = nextCost+heuristicValue(nextState)
                        random = Random()
                        cumulativeCost += int(random.random() * len(succs))
                        linkedList[nextState] = ({(currentState):linkedList[currentState]},currentState,nextState,nextMove,cumulativeCost,nextCost)
                        if searchtype == 2:
                            fringe.push(nextState,cumulativeCost)
                        else:
                            fringe.push(nextState)
                            
    def pathBuilder(self, linkedList, node, path):
        if node in linkedList:
            (childList,parent,nextState,action,cumulativeCost,nextCost) = linkedList.pop(node)
            if action <> None:
                path.append(action)
            self.pathBuilder(childList, parent, path)
        else:
            return path
        return path
    
    def nullHeuristic(self, state=None):
        """
        A heuristic function estimates the cost from the current state to the nearest
        goal in the provided SearchProblem.  This heuristic is trivial.
        """
        return 0
    
##############################################################


board = ["___","___","___"]
search = Search()
agent = Agent()
state = State(agent.index, board)
#problem = Problem(state)

print "Count: ", Agent.countAgent('_', state)

#succ = problem.getSuccessors(state)
succ = state.getSuccessors()

print "Succ: ", succ

path = search.aStarGenericSearch(state)

print "Path: ", path

action = Actions.ACTIONS[path[0]]

print str(action[0])+" "+str(action[1])

###############################################################

board = ["___","___","___"]
search = Search()
agent = ExpectimaxAgent()
state = State(agent.index, board)

print "Count: ", Agent.countAgent('_', state)
print "Index: ", agent.index, agent.getAgentSymbol()
path = agent.getAction(state)

print "Path: ", path
action = Actions.ACTIONS[path]
print str(action[0])+" "+str(action[1])

###############################################################